package test;

import java.util.Arrays;

public class SortNums {

    public static void main(String[] args) {
        int[] arr = {0,1,1,0,2,2};
        // 定义容器保存结果
        int n = 4;
        quickSort(arr,n,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickSort(int[] arr, int n, int left, int right) {
        if (left >= right){
            return;
        }
        int leftIndex = left;
        int rightIndex = right;
        int num = arr[left];
        while (leftIndex < rightIndex){
            while (leftIndex < rightIndex && compare(n,arr[rightIndex],num)){ // arr[rightIndex] >=  num
                rightIndex --;
            }
            while (leftIndex < rightIndex && !compare(n,arr[rightIndex],num)){ //arr[leftIndex] <= num
                leftIndex ++;
            }
            if (leftIndex < rightIndex){
                int temp = arr[leftIndex];
                arr[leftIndex] = arr[rightIndex];
                arr[rightIndex] = temp;
            }

        }

        arr[left] = arr[leftIndex];
        arr[leftIndex] = num;

        quickSort(arr, n, left,leftIndex - 1);
        quickSort(arr, n, leftIndex + 1,right);
    }

    private static boolean compare(int n, int a, int b) {
        int a1 = a % n;
        int b1 = b % n;
        if (a1 > b1){
            return true;
        }else if (a1 < b1){
            return false;
        }else {
            return a >= b;
        }
    }
}
